package com.programmercarl.tree;


/**
 * https://leetcode.cn/problems/maximum-binary-tree/description/
 *
 * @author yulongtian
 * @create 2024-12-23 13:59
 */
public class Test14 {
    public static void main(String[] args) {
        Test14 test14 = new Test14();
        TreeNode treeNode = test14.constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0, 5});
        System.out.println(treeNode.val);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        TreeNode treeNode = constructMaximumBinaryTree2(nums, 0, nums.length);// 左闭右开

        return treeNode;
    }

    public TreeNode constructMaximumBinaryTree2(int[] nums, int startIndex, int endIndex) {
        // 递归停止条件
        if (startIndex >= endIndex) {
            return null;
        }

        // 先找到最大值及其索引

        int biggestNumIndex = biggestNum(nums, startIndex, endIndex);
        // 创建本节点
        TreeNode treeNode = new TreeNode(nums[biggestNumIndex]);

        // 左边节点
        treeNode.left = constructMaximumBinaryTree2(nums, startIndex, biggestNumIndex);

        // 右边节点
        treeNode.right = constructMaximumBinaryTree2(nums, biggestNumIndex + 1, endIndex);

        // 返回本节点
        return treeNode;
    }

    public int biggestNum(int[] nums, int startIndex, int endIndex) {
        int maxVal = Integer.MIN_VALUE;
        int maxIndex = -1;
        for (int i = startIndex; i < endIndex; i++) {
            if (nums[i] > maxVal) {
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }

}
